#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

bool checkPartitioning(string s) {
    int n = s.size();
    vector<vector<bool>> f(n, vector<bool>(n));

    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            if (s[i] == s[j])
                f[i][j] = i + 1 < j ? f[i + 1][j - 1] : true;

    for (int i = 1; i < n - 1; i++)
        for (int j = i; j < n - 1; j++)
            if (f[0][i - 1] && f[i][j] && f[j + 1][n - 1])
                return true;
    return false;
}

int minCut(string s) {
    int n = s.size();
    vector<vector<bool>> f(n, vector<bool>(n));

    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++)
            if (s[i] == s[j])
                f[i][j] = i + 1 < j ? f[i + 1][j - 1] : true;

    vector<int> dp(n, n);
    for (int i = 0; i < n; i++)
        if (f[0][i])
            dp[i] = 0;
        else
            for (int j = 1; j <= i; j++)
                if (f[j][i])
                    dp[i] = min(dp[i], dp[j - 1] + 1);
    return dp[n - 1];
}

bool isMatch(string s, string p) {
    int n = s.size(), m = p.size();
    vector<vector<bool>> f(n + 1, vector<bool>(m + 1));
    s = ' ' + s, p = ' ' + p;
    f[0][0] = true;
    for (int i = 2; i <= m; i += 2)
        if (p[i] == '*') f[0][i] = true;
        else break;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (p[j] == '*')
                f[i][j] = f[i][j - 2] || (p[j - 1] == '.' || p[j - 1] == s[i]) && f[i - 1][j];
            else
                f[i][j] = (s[i] == p[j] || p[j] == '.') && f[i - 1][j - 1];
        }
    return f[n][m];
}